\documentstyle{article}
\setlength{\topmargin}{0in}
\setlength{\textheight}{8.5in}
\setlength{\oddsidemargin}{0in}
\setlength{\textwidth}{6.5in}
\newcommand{\cmt}[1]{{\sf [#1]}}
\newcommand{\SEC}[1]{\subsubsection*{#1}}
\begin{document}
\begin{center}
{\bf
GDR Programmer Documentation}\\
(last modification: 14 March 2002)
\end{center}

This document describes how to write an animated program for GDR.
A program implementing a graph algorithm is written in plain C with
macros and functions to access and animate the graph created by the user.
The declarations needed for interfacing with GDR are provided by an
\mbox{\tt \#include "Gdr.h"} statement.
The code that is to be executed by the user is written as a
parameterless procedure {\tt animat()}.
Examples of previously written animations can be found in files {\tt
bicon.c, dfa.c, dfs\_d.c, nfa.c}, and {\tt prim.c}.

The first step is to code the graph algorithm in C using graph traversal
macros where appropriate.
GDR provides the following traversal macros (the definitions for these
are found in {\tt def.h}:
\begin{itemize}
\item
{\tt for\_adjacent(v,e,w)} creates a loop whose body is executed once for
each outgoing edge $e$ from vertex $v$ --- the vertex $w$ is the other
endpoint of $e$ (for undirected graphs, all edges incident to $v$ are
traversed).

\item
{\tt for\_incoming\_edges(v,e,u)} traverses all edges $e=(u,v)$ leding
into $v$ (in the case of undirected graphs, this is identical to {\tt
for\_adjacent}).

\item
{\tt for\_all\_vertices(v)} accesses all valid vertices $v$

\item
{\tt for\_all\_edges(e)} accesses all edges $e$ 
\end{itemize}
In GDR a graph is a set of edges --- multiple edges between the same two
vertices are allowed.
The above macros may not work correctly if the graph is modified in the
loop body, e.g. if edges are deleted.  More careful implementation using
the functions {\tt first\_out\_edge} and {\tt next\_out\_edge} may be required.
Tables~\ref{tab:logical} and \ref{tab:change} list all the GDR functions
for accessing and changing graph structure.

\begin{table}
\caption{Access to Logical Graph Attributes in GDR}
\label{tab:logical}
\begin{center}
\small
\begin{tabular}{|l | p{3.0in}|}
\hline
	\verb$max_vertex()$ & returns the maximum vertex id possible
        (current implementation does not guarantee that it's valid)\\\hline

	\verb$is_valid_vertex(vertex:v)$ & returns TRUE if v is a valid vertex, 
	    FALSE otherwise (the vertex whose id is v may have been deleted)
    \\\hline

	\verb$get_a_vertex()$ & returns the first valid vertex in the graph\\\hline

	\verb$are_edges_equal(edge:e1,e2)$ & returns TRUE if the edges are
        the same, FALSE otherwise\\\hline

	\verb$head(edge:e)$ & returns the vertex to which \verb$e$ is
    directed (the second vertex to be added to \verb$e$ in case of an
    undirected edge)\\\hline

	\verb$tail(edge:e)$ & returns the vertex from which \verb$e$ is
    directed (the first vertex to be added to \verb$e$ in case of an
    undirected edge)\\\hline

	\verb$other_vertex(vertex:v,edge:e)$ & returns the vertex that along with
    \verb$v$ defines the edge \verb$e$\\\hline

	\verb$first_out_edge(vertex:v)$ & returns the first outgoing edge
        from vertex \verb$v$ (first edge on \verb$v$'s adjacency list if
        undirected graph)\\\hline

	\verb$next_out_edge(vertex:v,edge:e)$ & returns the next outgoing edge
         after \verb$e$ from vertex \verb$v$ (to be used in conjunction
         with \verb$first_out_edge$ for sequential access of adjacency
         lists)\\\hline 

	\verb$first_in_edge(vertex:v)$ & returns the first edge into vertex
        \verb$v$ (for directed graphs; first edge on v's adjacency list
        if undirected)\\\hline 

	\verb$next_in_edge(vertex:v,edge:e)$ & returns the next edge after
        \verb$e$ going into vertex \verb$v$ (analogous to
        \verb$next_out_edge$)\\\hline 

	\verb$first_edge()$ & returns the first edge from the list of all edges
    	in the graph\\\hline

	\verb$next_edge(edge:e)$ & returns the next edge after \verb$e$
         in the list of all edges\\\hline

	\verb$vertex_label(vertex:v)$ & returns the label of vertex {\tt v} in
         an allocated string\\\hline

	\verb$edge_label(edge:e)$ & returns the label of edge {\tt e} in
         an allocated string\\\hline
\end{tabular}
\end{center}
\end{table}

\begin{table}
\caption{Changing Logical Graph Attributes in GDR}
\label{tab:change}
\begin{center}
\small
\begin{tabular}{|l | p{2.5in}|}
\hline
    \verb$add_vertex(int:x,y;string:label)$ &
    adds a new vertex and returns its id;
    the vertex is drawn at position \verb$(x,y)$ and is given \verb$label$ as
    its label\\\hline

	\verb$add_edge(vertex:v1,v2;string:label)$ &
    adds a new edge from \verb$v1$ to \verb$v2$ and returns its id;
    label of the new edge is \verb$label$\\\hline

	\verb$delete_vertex(vertex:v)$ & deletes vertex \verb$v$ and all incident
	edges from the graph\\\hline

	\verb$delete_edge(edge:e)$ & deletes edge \verb$e$ from the graph\\\hline

	\verb$change_vertex_label(vertex:v;string:label)$ & changes the
        label of {\tt v} to {\tt label}\\\hline

	\verb$change_edge_label(edge:e;string:label)$ & changes the label of
        {\tt e} to {\tt label}\\\hline
\end{tabular}
\end{center}
\end{table}

Animations are created by changing the logical structure, geometry, or
display characteristics of a graph in response to actions taken by the
algorithm.
Simple animations can be created by highlighting vertices and edges, by
exposing or hiding their labels, or by changing the text of the labels.
The functions to do this are described in Table~\ref{tab:display} (the
functions for changing labels are described in Table~\ref{tab:change}).

\begin{table}
\caption{Access to Display Attributes in GDR}
\label{tab:display}
\begin{center}
\small
\begin{tabular}{|l | p{3.0in}|}
\hline
	\verb$is_highlighted_vertex(vertex:v)$ & returns {\tt TRUE}
         if the vertex {\tt v} is highlighted
\\\hline	
	\verb$is_highlighted_edge(edge:e)$ & returns {\tt TRUE} if the
         edge {\tt e} is highlighted
\\\hline
	\verb$is_exposed_vertex_label(vertex:v)$ & returns {\tt TRUE} if the
        label of vertex {\tt v} is exposed
\\\hline	
	\verb$is_exposed_edge_label(edge:e)$ & returns {\tt TRUE} if the
        label of edge {\tt e} is exposed
\\\hline
	\verb$highlight_vertex(vertex:v)$ & highlights vertex {\tt v}, i.e.
        makes its background white
\\\hline	
	\verb$un_highlight_vertex(vertex:v)$ & removes highlighting from vertex
         {\tt v}, i.e. makes its background black
\\\hline
	\verb$highlight_edge(edge:e)$ & highlights edge {\tt e}, i.e.
        fattens all of the line segments representing {\tt e}
\\\hline	
	\verb$un_highlight_edge(edge:e)$ & removes highlighting from edge
        {\tt e}, i.e. represents the edge as line segments of thickness~1
\\\hline
	\verb$expose_vertex_label(vertex:v)$ & causes the vertex label of
        {\tt v} to appear on the display
\\\hline
	\verb$expose_edge_label(edge:e)$ & causes the edge label of {\tt e}
        to appear on the display
\\\hline
	\verb$hide_vertex_label(vertex:v)$ & causes the vertex label of {\tt
        v} to be erased from the display
\\\hline
	\verb$hide_edge_label(edge:e)$ & causes the edge label of {\tt e} to
        be erased from the display
\\\hline
\end{tabular}
\end{center}
\end{table}

Table~\ref{tab:misc} shows other useful functions for interacting with
the display of the graph.
Vertices and edges can be blinked (the delay of a blink is controlled by
a compile-time parameter {\tt BLINK\_DELAY} in {\tt gr.h}).
Windows to display text can be created and manipulated.
Pauses for user response can be added using {\tt suspend\_animation} (a
general pause mechanism), {\tt get\_xy\_from\_mouse} (to query user for a
position), or {\tt select\_vertex} (to have user point to a vertex).

\begin{table}
\caption{Miscellaneous Programmer Functions in GDR}
\label{tab:misc}
\begin{center}
\small
\begin{tabular}{|l | p{2.5in}|}
\hline
	\verb$blink_vertex(vertex:v,int:count)$ & causes vertex {\tt
        v} to blink (change from unhighlighted to highlighted and back)
        {\tt count} times  
\\\hline	
	\verb$blink_edge(edge:e,int:delay,count)$ & causes edge {\tt e} to blink
        (details same as vertex blinking)
\\\hline
	\verb$print_graph_data(string:name;flag:append)$ & outputs the
    current graph, in GDR format, to file {\tt name};
	if {\tt append} is {\tt TRUE}, the
	existing file gets appended, else it is overwritten
    (can be used for automatic generation of stills from animation)
\\\hline
	\verb$suspend_animation()$ & gives control back to edit mode;
	program execution is resumed when user clicks left in the {\tt
    RESUME ?} window or presses {\tt q} or {\tt Q}
\\\hline
	\verb$create_text_window(int:x,y;string:message)$ & creates a window
    with upper left corner at
	postion {\tt (x,y)} and {\tt message} written into it ({\tt message}
    can have
	multiple lines, delimited by \verb$\n$), and returns a window identifier
    (type {\tt Window})
\\\hline
	\verb$write_text_window(Window:w,string:message)$ & changes the
        content of window {\tt w} to {\tt message} and causes window
        {\tt w} to appear (if hidden)
\\\hline
	\verb$hide_window(Window:w)$ & makes window {\tt w} disappear from view
\\\hline
	\verb$kill_window(Window:w)$ & destroys the window {\tt w} and unmaps
    it in the process; warning: any further references to the window
    indentifier {\tt w} will result in
	an X Window Protocol error.
\\\hline
	\verb$get_xy_from_mouse(int reference:x,y)$ & prompts user to click 
	the mouse and the x and y coordinates are passed back by reference
    (returns {\tt FALSE}
    if user hits 
	{\tt [Control-C]} to abort, else returns {\tt TRUE})
\\\hline
    \verb$select_vertex()$ & returns the id of a vertex selected by
        left mouse click or {\tt NULL\_VERTEX} if user typed {\tt q}
        before clicking the mouse
\\\hline
    \verb$query(int: x,y; string:msg,ans)$ & prints msg in a box at
position $(x,y)$ and returns what the user typed through ans; the actual
value returned is a flag indicating a response other than \^C
\\\hline
\end{tabular}
\end{center}
\end{table}

GDR also gives the programmer access to the geometry of the displayed
graph --- for details, see Table~\ref{tab:geometric}.

\begin{table}
\caption{Access to Geometric Attributes in GDR}
\label{tab:geometric}
\begin{center}
\small
\begin{tabular}{|l | p{2.6in}|}
\hline
    \verb$add_vertex(int:x,y;string:label)$ &
    adds a new vertex and returns its id;
    the vertex is drawn at position \verb$(x,y)$ and is given \verb$label$ as
    its label\\\hline

	\verb$vertex_x(vertex:v)$ & returns the x-coordinate of the vertex \verb$v$
\\\hline
	\verb$vertex_y(vertex:v)$ & returns the y-coordinate of the vertex \verb$v$
\\\hline
	\verb$move_vertex_relative(vertex:v;int:d_x,d_y)$ & moves the 
	vertex \verb$v$ to the right \verb$d_x$ units and down \verb$d_y$
    units (left and/or up if negative numbers are used); also
	moves the associated edges; returns \verb$FALSE$ on error, else returns
	\verb$TRUE$
\\\hline
        \verb$edge_label_x(edge:e)$ & returns the x-coordinate of the
        label of edge \verb$e$
\\\hline
        \verb$edge_label_y(edge:e)$ & returns the y-coordinate of the
        label of edge \verb$e$
\\\hline
        \verb$move_edge_label(edge:e;int:x,y)$ & moves the edge label of
        \verb$e$ so that it is centered at point $(x,y)$
\\\hline
	\verb$window_width()$ &	returns the width of the graph display area
\\\hline	
	\verb$window_height()$ & returns the height of the graph display area
\\\hline
\end{tabular}
\end{center}
\end{table}

Suppose an animated program for directed graphs
has been written in file {\tt alg.c}.
It can be compiled and linked with GDR using the following commands
\begin{verbatim}
        cc -c -I/usr/include/X11 alg.c
	cc -c -I/usr/include/X11 -DICON='"Title Bar"' -DDIRECTED gr.c
	cc -o alg gr.o gr_tool.o pane.o list.o alg.o -lX11 -lm
\end{verbatim}
This assumes that {\tt gr\_tool.c, pane.c,} and {\tt list.c} have
already been compiled (using an incantation like that of the first line above).
The {\tt -I/usr/include/X11} indicates the directory where X11 header
fiels are to be found, {\tt -DICON='"Title Bar"'} causes the given text
to appear in the icon and the title bar of the GDR window (if this is
omitted, the title bar just has the name GDR), and {\tt -DDIRECTED} is
omitted if the program deals with undirected graphs.
The program {\tt alg} then becomes a version of GDR customized to run
the animation supplied by the programmer in {\tt alg.c}.

Another alternative is to add an entry for alg in the {\tt Makefile},
and then invoke the command {\tt make alg}.

Further customizations can be done by editing the file {\tt gr.h} (be
sure to recompile everything when you do this).

\cmt{make a list of the sorts of things that can be customized}
\cmt{explain blink delays and blink ratio}
\end{document}
